package com.cat.dataStructure;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/minimum-operations-to-make-all-array-elements-equal/description/
 * @create 2025/8/19 16:21
 * @since JDK17
 */

public class Solution38 {
    public List<Long> minOperations(int[] nums, int[] queries) {
        List<Long> ans = new ArrayList<>();
        int n = nums.length, m = queries.length;
        long[] prefix = new long[n + 1];
        Arrays.sort(nums);
        for (int i = 0; i < n; i++) {   // 求出前缀和
            prefix[i + 1] = prefix[i] + nums[i];
        }
        for (int i = 0, idx; i < m; i++) {
            idx = Arrays.binarySearch(nums, queries[i]);
            idx = idx < 0 ? -idx - 1 : idx; //
            long left = (long) idx * queries[i] - prefix[idx];
            long right = prefix[n] - prefix[idx] - (long)(n - idx) * queries[i];
            ans.add(left + right);
        }

        return ans;
    }
}

